package 二叉树;

import Utils.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author TTDB
 * @create 2025/9/18
 */
public class pathSum {
     private int ans;
     public int pathSum(TreeNode root, int targetSum){
          if(root == null) return 0;
          Map<Long, Integer> cnt = new HashMap<>();
          cnt.put(0L, 1);
          dfs(root, targetSum, 0, cnt);
          return ans;
     }
     void dfs(TreeNode root, int targetSum, long sum, Map<Long, Integer> cnt){
          if(root == null) return;
          sum += root.val;
          //前缀和统计
          ans += cnt.getOrDefault(sum - targetSum, 0);
          cnt.merge(sum, 1, Integer::sum);//记录当前前缀和
          dfs(root.left, targetSum, sum, cnt);
          dfs(root.right, targetSum, sum, cnt);
          cnt.merge(sum, -1, Integer::sum);//恢复
     }
}
